/*AC
  http://code.google.com/codejam/contest/32016/dashboard#s=p2

  (3+sqrt(5))^n+(3-sqrt(5))^n= A^N*(2,6)
  A={{0,1},{-4,6}}

  to calc power N
  0. calc storage[n] with A^n n=(1,2,4,8,16...,64)
  1. N=N-1
  2. make N -> binrary, for example N->1101
  3. check each bit in N so, 1101= A^8*A^4*A^1=result
  4. finally, result*(2,6)
  5. if result < 0 then result += 1000
  6. print result-1
*/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

void MatrixMul(int a[2][2],int b[2][2],int result[2][2]);
void MatrixCopy(int result[2][2],int b[2][2]);
void MatrixPrintf(int a[2][2]);
void ResultPrint(int caseNumber,int number);

int main() 
{ 

#ifdef FILEIO
  freopen("in.txt","r",stdin); 
  freopen("out.txt","w",stdout); 
#endif

  int a[2][2] = {{0,1},{-4,6}};
  int b[2][2] = {0};
  int result[2][2] = {{1,0},{0,1}};
  int ONE[2][2]={{1,0},{0,1}};
  int resulttemp[2][2] = {0};
  int storage[64][2][2] = {0};
  int bits[64] = {0};

  int i,j,k;

  int caseNumber=1;
  int finalResult = 0;

  long long temp=0;
  int N;
  MatrixCopy(storage[0],a);
  for(i = 1;i<64;i++)
    {
      MatrixMul(storage[i - 1],storage[i - 1],storage[i]);
    }

  //  MatrixMul(a,a,result);
  //  MatrixCopy(storage[0],result);
  //  MatrixPrintf(storage[0]);
  scanf("%d\n",&N);
  while(N--) 
    {
	  temp=0;
      scanf("%ld",&temp);
      temp = temp - 1;
      memset(bits,0,64*sizeof(int));
      
      for(i = 0;i<64;i++)
        {
          bits[i] = temp & 1;
          temp = temp>>1;
        }

      for(i = 0;i<64;i++)
        {
          if(bits[i] == 1) 
            {
              MatrixMul(result,storage[i],resulttemp);
              MatrixCopy(result,resulttemp);
            }
        }

      finalResult = (2*result[1][0] + 6*result[1][1])%1000;
      if(finalResult<0)
        finalResult += 1000; 
      ResultPrint(caseNumber++,finalResult-1);
      MatrixCopy(result,ONE);
    }

  
  

  //  printf("%d\n",sizeof(long long)); long long is 8

#ifdef FILEIO
  fclose(stdin);
  fclose(stdout);
#endif
  
  return 0; 
}

void MatrixCopy(int b[2][2],int result[2][2])
{
  int i,j,k;
  for(i = 0;i<2;i++)
    for(j = 0;j<2;j++)
      {
        b[i][j] = result[i][j];
      }
}

void MatrixMul(int a[2][2],int b[2][2],int result[2][2])
{
  int i,j,k;
  for(i = 0;i<2;i++)
    for(j = 0;j<2;j++)
      {
        result[i][j] = 0;
        for(k = 0;k<2;k++)
          {
            result[i][j] += a[i][k]*b[k][j];
            result[i][j] %= 1000;
          }
      }
}
void MatrixPrintf(int a[2][2])
{
  int i,j;
  for(i = 0;i<2;i++)
    {
      for(j = 0;j<2;j++)
        {
          printf("%d ",a[i][j]);
        }
      printf("\n");
    } 
}

void ResultPrint(int caseNumber,int number)
{
  int buf[3] = {0,0,0};
  if(number>1000)
    {
      exit(1);
    }

  int temp = number;
  int i = 2;
  while(temp)
    {
      buf[i--] = temp%10;
      temp = temp/10;
    }

  printf("Case #%d: ",caseNumber);
  for(i = 0;i<3;i++)
    printf("%d",buf[i]);
  printf("\n");
}
